package pers.vic.basics.leetcode;

/**
 * @author Vic.xu
 * @description: 86. 分隔链表  {@literal https://leetcode-cn.com/problems/partition-list/}
 * @date: 2021/2/24 0024 9:00
 */
public class J0086_M_Partition {
    /*
    给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，
    使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
    你应当 保留 两个分区中每个节点的初始相对位置。
    输入：head = [1,4,3,2,5,2], x = 3
    输出：[1,2,2,4,3,5]
     */

    /**
     * 利用哨兵保持原来的节点相对顺序
     */
    public static ListNode partition(ListNode head, int x) {
        //小于x的节点
        ListNode less = new ListNode();
        ListNode curLess = less;
        //不小于x的节点
        ListNode more = new ListNode();
        ListNode curMore = more;
        ListNode cur = head;
        while (cur != null) {
            int val = cur.val;
            ListNode node = new ListNode(val);
            if (val < x) {
                curLess.next = node;
                curLess = curLess.next;
            }else {
                curMore.next = node;
                curMore = curMore.next;
            }
            cur = cur.next;
        }
        curLess.next = more.next;
        return less.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(new int[]{1,4,3,2,5,2});
        System.out.println(head);
        ListNode partition = partition(head, 3);
        System.out.println(partition);


    }

}
